<html>
<head>
  <title>Evernote Export</title>
  <basefont face="微软雅黑" size="2" />
  <meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
  <meta name="exporter-version" content="YXBJ Windows/601748 (zh-CN, DDL); Windows/10.0.0 (Win64); EDAMVersion=V2;"/>
  <style>
    body, td {
      font-family: 微软雅黑;
      font-size: 10pt;
    }
  </style>
</head>
<body>
<a name="8544"/>

<div>
<span><div><span style="font-size: 12pt;"><a href="https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/yi-ge-fang-fa-tuan-mie-6-dao-gu-piao-wen-ti-by-l-3/">https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/yi-ge-fang-fa-tuan-mie-6-dao-gu-piao-wen-ti-by-l-3/</a></span></div><div><font style="font-size: 12pt;"><br/></font></div><div><span style="font-size: 16px;">状态转移问题： </span></div><div><font style="font-size: 12pt;">dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])</font></div><div><font style="font-size: 12pt;">              max(   选择 rest  ,           选择 sell      )</font></div><div><font style="font-size: 12pt;"><br/></font></div><div><font style="font-size: 12pt;">解释：今天我没有持有股票，有两种可能：</font></div><div><font style="font-size: 12pt;">要么是我昨天就没有持有，然后今天选择 rest，所以我今天还是没有持有；</font></div><div><font style="font-size: 12pt;">要么是我昨天持有股票，但是今天我 sell 了，所以我今天没有持有股票了。</font></div><div><font style="font-size: 12pt;"><br/></font></div><div><font style="font-size: 12pt;">dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])</font></div><div><font style="font-size: 12pt;">              max(   选择 rest  ,           选择 buy         )</font></div><div><font style="font-size: 12pt;"><br/></font></div><div><font style="font-size: 12pt;">解释：今天我持有着股票，有两种可能：</font></div><div><font style="font-size: 12pt;">要么我昨天就持有着股票，然后今天选择 rest，所以我今天还持有着股票；</font></div><div><font style="font-size: 12pt;">要么我昨天本没有持有，但今天我选择 buy，所以今天我就持有股票了。</font></div><div><font style="font-size: 12pt;"><br/></font></div><div><span style="font-size: 16px;"><b>第一种情况：  k = 1 </b></span></div><div><span style="font-size: 16px;">即： 只能交易一次</span></div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.15);-en-codeblock:true;"><div><font style="font-size: 11pt;">class Solution {</font></div><div><font style="font-size: 11pt;">public:</font></div><div><font style="font-size: 11pt;">        // k =1 的情况</font></div><div><font style="font-size: 11pt;">        int maxProfit(vector&lt;int&gt;&amp; prices) {</font></div><div><font style="font-size: 11pt;">               if (prices.size() == 0 || prices.size() == 1) {</font></div><div><font style="font-size: 11pt;">                       return 0;</font></div><div><font style="font-size: 11pt;">               }</font></div><div><font style="font-size: 11pt;">               int n = prices.size();</font></div><div><font style="font-size: 11pt;">               // dp[i][0] 表示第i天没有股票在手， dp[i][1] 表示第i天有股票在手</font></div><div><font style="font-size: 11pt;">               vector&lt;vector&lt;int&gt;&gt; dp(n, vector&lt;int&gt;(2));</font></div><div><font style="font-size: 11pt;">               for (int i = 0; i &lt; n; i++) {</font></div><div><font style="font-size: 11pt;">                       if (i - 1 == -1) {</font></div><div><font style="font-size: 11pt;">                              dp[i][0] = 0;</font></div><div><font style="font-size: 11pt;">                              continue;</font></div><div><font style="font-size: 11pt;">                       }</font></div><div><font style="font-size: 11pt;">                       dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);</font></div><div><font style="font-size: 11pt;">                       dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);</font></div><div><font style="font-size: 11pt;">               }</font></div><div><font style="font-size: 11pt;">               return dp[n - 1][0];</font></div><div><font style="font-size: 11pt;">        }</font></div><div><font style="font-size: 11pt;">        // 优化版本</font></div><div><font style="font-size: 11pt;">        int maxProfit(vector&lt;int&gt;&amp; prices) {</font></div><div><font style="font-size: 11pt;">               if (prices.size() == 0 || prices.size() == 1) {</font></div><div><font style="font-size: 11pt;">                       return 0;</font></div><div><font style="font-size: 11pt;">               }</font></div><div><font style="font-size: 11pt;">               int n = prices.size();</font></div><div><font style="font-size: 11pt;">               // base case : dp[i][0] = 0， dp[i][1] = -infinity</font></div><div><font style="font-size: 11pt;">               int dp_i_0 = 0, dp_i_1 = INT_MIN;</font></div><div><font style="font-size: 11pt;">               for (int i = 0; i &lt; n; i++) {</font></div><div><font style="font-size: 11pt;">                       dp_i_0 = max(dp_i_0, dp_i_1 + prices[i]);</font></div><div><font style="font-size: 11pt;">                       dp_i_1 = max(dp_i_1, -prices[i]);</font></div><div><font style="font-size: 11pt;">               }</font></div><div><font style="font-size: 11pt;">               return dp_i_0;</font></div><div><font style="font-size: 11pt;">        }</font></div><div><font style="font-size: 11pt;">}</font></div></div><div><span style="font-size: 16px;"><b><br/></b></span></div><div><span style="font-size: 16px;"><b>第二种情况：k = +infinity</b></span></div><div><font style="font-size: 12pt;"><br/></font></div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.15);-en-codeblock:true;"><div><font style="font-size: 12pt;">class Solution {</font></div><div><font style="font-size: 12pt;">public:</font></div><div><font style="font-size: 12pt;">    int maxProfit(vector&lt;int&gt;&amp; prices) {</font></div><div><font style="font-size: 12pt;">        if (prices.size() == 0 || prices.size() == 1) {</font></div><div><font style="font-size: 12pt;">            return 0;</font></div><div><font style="font-size: 12pt;">        }</font></div><div><font style="font-size: 12pt;">        int n = prices.size();</font></div><div><font style="font-size: 12pt;">        vector&lt;vector&lt;int&gt;&gt; dp(n, vector&lt;int&gt;(2));</font></div><div><font style="font-size: 12pt;">        dp[0][0] = 0;</font></div><div><font style="font-size: 12pt;">        dp[0][1] = -prices[0];   // 这里不能使用INT_MIN</font></div><div><font style="font-size: 12pt;">        for (int i = 1; i &lt; n; i++) {</font></div><div><font style="font-size: 12pt;">            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);</font></div><div><font style="font-size: 12pt;">            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);</font></div><div><font style="font-size: 12pt;">        }</font></div><div><font style="font-size: 12pt;">        return dp[n - 1][0];</font></div><div><font style="font-size: 12pt;">        </font></div><div><font style="font-size: 12pt;">    }</font></div><div><font style="font-size: 12pt;">};</font></div><div><span style="font-size: 12pt; color: rgb(51, 51, 51); font-family: Monaco;">// 优化版本</span></div><div><font style="font-size: 12pt;">class Solution {</font></div><div><font style="font-size: 12pt;">public:</font></div><div><font style="font-size: 12pt;">    int maxProfit(vector&lt;int&gt;&amp; prices) {</font></div><div><font style="font-size: 12pt;">       int n = prices.size();</font></div><div><font style="font-size: 12pt;">       int dp_i_0 = 0, dp_i_1 = INT_MIN;</font></div><div><font style="font-size: 12pt;">       for (int i = 0; i &lt; n; i++) {</font></div><div><font style="font-size: 12pt;">           int temp = dp_i_0;</font></div><div><font style="font-size: 12pt;">           dp_i_0 = max(dp_i_0, dp_i_1 + prices[i]);</font></div><div><font style="font-size: 12pt;">           dp_i_1 = max(dp_i_1, temp - prices[i]);</font></div><div><font style="font-size: 12pt;"> <span>    </span><span>  </span>}</font></div><div><font style="font-size: 12pt;">       return dp_i_0;</font></div><div><font style="font-size: 12pt;">    }</font></div><div><font style="font-size: 12pt;">};</font></div></div><div><font style="font-size: 12pt;"><br/></font></div><div><font style="font-size: 12pt;"><b><br/></b></font></div><div><span style="font-size: 12pt;"><b>第三种情况，k = +infinity with cooldown （冷冻期）</b></span></div><div><span style="font-size: 12pt;"><br/></span></div><div><span style="font-size: 12pt;">dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])</span></div><div><span style="font-size: 12pt;">dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])</span></div><div><span style="font-size: 12pt;">解释：第 i 天选择 buy 的时候，要从 i-2 的状态转移，而不是 i-1 。</span></div><div><span style="font-size: 12pt;"><br/></span></div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.15);-en-codeblock:true;"><div><font style="font-size: 11pt;">class Solution {</font></div><div><font style="font-size: 11pt;">public:</font></div><div><font style="font-size: 11pt;">    int maxProfit(vector&lt;int&gt;&amp; prices) {</font></div><div><font style="font-size: 11pt;">        int n = prices.size();</font></div><div><font style="font-size: 11pt;">        int dp_i_0 = 0, dp_i_1 = INT_MIN;</font></div><div><font style="font-size: 11pt;">        int dp_pre_0 = 0; // 代表 dp[i-2][0]</font></div><div><font style="font-size: 11pt;">        for (int i = 0; i &lt; n; i++) {</font></div><div><font style="font-size: 11pt;">            int temp = dp_i_0;</font></div><div><font style="font-size: 11pt;">            dp_i_0 = max(dp_i_0, dp_i_1 + prices[i]);</font></div><div><font style="font-size: 11pt;">            dp_i_1 = max(dp_i_1, dp_pre_0 - prices[i]);</font></div><div><font style="font-size: 11pt;">            dp_pre_0 = temp;</font></div><div><font style="font-size: 11pt;">        }</font></div><div><font style="font-size: 11pt;">        return dp_i_0;</font></div><div><font style="font-size: 11pt;">    }<br/></font></div><div><font style="font-size: 11pt;">};</font></div></div><div><font style="font-size: 12pt;"><b><br/></b></font></div><div><b><span style="font-size: 16px;">第四种情况： </span><span style="font-size: 12pt;">k = +infinity with fee (手续费）</span></b></div><div><span style="font-size: 12pt;">dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])</span></div><div><span style="font-size: 12pt;">dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i] - fee)</span></div><div><span style="font-size: 12pt;">解释：相当于买入股票的价格升高了。</span></div><div><font style="font-size: 12pt;">在第一个式子里减也是一样的，相当于卖出股票的价格减小了。</font></div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.15);-en-codeblock:true;"><div><font style="font-size: 12pt;">class Solution {</font></div><div><font style="font-size: 12pt;">public:</font></div><div><font style="font-size: 12pt;">    int maxProfit(vector&lt;int&gt;&amp; prices, int fee) {</font></div><div><font style="font-size: 12pt;">        int n = prices.size();</font></div><div><font style="font-size: 12pt;">        int dp_i_0 = 0, dp_i_1 = INT_MIN;</font></div><div><font style="font-size: 12pt;">        for (int i = 0; i &lt; n; i++) {</font></div><div><font style="font-size: 12pt;">            int temp = dp_i_0;</font></div><div><font style="font-size: 12pt;">            dp_i_0 = max(dp_i_0, dp_i_1 + prices[i]);</font></div><div><font style="font-size: 12pt;">            dp_i_1 = max(dp_i_1, temp - prices[i] - fee);</font></div><div><font style="font-size: 12pt;">        }</font></div><div><font style="font-size: 12pt;">        return dp_i_0;</font></div><div><font style="font-size: 12pt;">    }</font></div><div><font style="font-size: 12pt;">};</font></div></div><div><span style="font-size: 16px;"><b><br/></b></span></div><div><b><span style="font-size: 16px;">第5种情况：</span><span style="font-size: 12pt;">k = 2 （可以一天内交易两次）</span></b></div><div><span style="font-size: 12pt;"><br/></span></div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.15);-en-codeblock:true;"><div> //dp[i][2][0] = max(dp[i - 1][2][0], dp[i - 1][2][1] + prices[i])</div><div> //dp[i][2][1] = max(dp[i - 1][2][1], dp[i - 1][1][0] - prices[i])</div><div> //dp[i][1][0] = max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])</div><div> //dp[i][1][1] = max(dp[i - 1][1][1], -prices[i])</div><div><font style="font-size: 11pt;">class Solution {</font></div><div><font style="font-size: 11pt;">public:</font></div><div><font style="font-size: 11pt;">    int maxProfit(vector&lt;int&gt;&amp; prices) {</font></div><div><font style="font-size: 11pt;">        int dp_i10 = 0, dp_i11 = INT_MIN;</font></div><div><font style="font-size: 11pt;">        int dp_i20 = 0, dp_i21 = INT_MIN;</font></div><div><font style="font-size: 11pt;">        for (int price : prices) {</font></div><div><font style="font-size: 11pt;">            dp_i20 = max(dp_i20, dp_i21 + price);</font></div><div><font style="font-size: 11pt;">            dp_i21 = max(dp_i21, dp_i10 - price);</font></div><div><font style="font-size: 11pt;">            dp_i10 = max(dp_i10, dp_i11 + price);</font></div><div><font style="font-size: 11pt;">            dp_i11 = max(dp_i11, -price);</font></div><div><font style="font-size: 11pt;">        }</font></div><div><font style="font-size: 11pt;">        return dp_i20;</font></div><div><font style="font-size: 11pt;">    }</font></div><div><font style="font-size: 11pt;">};</font></div></div><div><font style="font-size: 12pt;"><b><br/></b></font></div><div><b><span style="font-size: 16px;">第6种情况： </span><span style="font-size: 12pt;">k = any integer （随便交易次数）</span></b></div><div><span style="font-size: 12pt;">一次交易由买入和卖出构成，至少需要两天。所以说有效的限制 k 应该不超过 n/2，如果超过，就没有约束作用了，相当于 k = +infinity。这种情况是之前解决过的。</span></div><div><span style="font-size: 12pt;"><br/></span></div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.15);-en-codeblock:true;"><div><font style="font-size: 11pt;">class Solution {</font></div><div><font style="font-size: 11pt;">public:</font></div><div><font style="font-size: 11pt;">    int maxProfit(int max_k, vector&lt;int&gt;&amp; prices) {</font></div><div><font style="font-size: 11pt;">        int n = prices.size();</font></div><div><font style="font-size: 11pt;">        if (max_k &gt; n / 2) // k属于 无穷， 一定要，不然出错</font></div><div><font style="font-size: 11pt;">            return maxProfit_k_inf(prices);</font></div><div><font style="font-size: 11pt;">        vector&lt;vector&lt;vector&lt;int&gt; &gt; &gt; dp(n, vector&lt;vector&lt;int&gt;&gt;(max_k+1, vector&lt;int&gt;(2)));</font></div><div><font style="font-size: 11pt;">        for (int i = 0; i &lt; n; i++)</font></div><div><font style="font-size: 11pt;">            for (int k = max_k; k &gt;= 1; k--) {</font></div><div><font style="font-size: 11pt;">                if (i - 1 == -1) {</font></div><div><font style="font-size: 11pt;">                    /* 处理 base case */</font></div><div><font style="font-size: 11pt;">                    dp[i][k][0] = 0;</font></div><div><font style="font-size: 11pt;">                    dp[i][k][1] = -prices[i];</font></div><div><font style="font-size: 11pt;">                    continue;</font></div><div><font style="font-size: 11pt;">                }</font></div><div><font style="font-size: 11pt;">                dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);</font></div><div><font style="font-size: 11pt;">                dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);</font></div><div><font style="font-size: 11pt;">            }</font></div><div><font style="font-size: 11pt;">        return dp[n - 1][max_k][0];</font></div><div><font style="font-size: 11pt;">    }</font></div><div><font style="font-size: 11pt;">    int maxProfit_k_inf(vector&lt;int&gt; prices) {</font></div><div><font style="font-size: 11pt;">        int n = prices.size();</font></div><div><font style="font-size: 11pt;">        int dp_i_0 = 0, dp_i_1 = INT_MIN;</font></div><div><font style="font-size: 11pt;">        for (int i = 0; i &lt; n; i++) {</font></div><div><font style="font-size: 11pt;">            int temp = dp_i_0;</font></div><div><font style="font-size: 11pt;">            dp_i_0 = max(dp_i_0, dp_i_1 + prices[i]);</font></div><div><font style="font-size: 11pt;">            dp_i_1 = max(dp_i_1, temp - prices[i]);</font></div><div><font style="font-size: 11pt;">        }</font></div><div><font style="font-size: 11pt;">        return dp_i_0;</font></div><div><font style="font-size: 11pt;">    }</font></div><div><font style="font-size: 11pt;">};</font></div></div><div><br/></div></span>
</div></body></html> 